home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / unix / volume3 / pathalias2 / part2 < prev    next >
Encoding:
Internet Message Format  |  1986-11-30  |  49.9 KB
  1. Subject: New pathalias, part 2 of 2
  2. Newsgroups: mod.sources
  3. Approved: jpn@panda.UUCP
  4.  
  5. Mod.sources:  Volume 3, Issue 93
  6. Submitted by: princeton!down!honey (Peter Honeyman)
  7.  
  8. #! /bin/sh
  9. # This is a shell archive, meaning:
  10. # 1. Remove everything above the #! /bin/sh line.
  11. # 2. Save the resulting text in a file.
  12. # 3. Execute the file with /bin/sh (not csh) to create the files:
  13. #    addlink.c
  14. #    addnode.c
  15. #    extern.c
  16. #    local.c
  17. #    main.c
  18. #    makedb.c
  19. #    mapaux.c
  20. #    mapit.c
  21. #    mem.c
  22. #    printit.c
  23. #    parse.y
  24. # This archive created: Wed Jan 22 18:53:16 1986
  25. export PATH; PATH=/bin:$PATH
  26. echo shar: extracting "'addlink.c'" '(3358 characters)'
  27. if test -f 'addlink.c'
  28. then
  29.     echo shar: will not over-write existing file "'addlink.c'"
  30. else
  31. cat << \SHAR_EOF > 'addlink.c'
  32. /* pathalias -- by steve bellovin, as told to peter honeyman */
  33. #ifndef lint
  34. static char    *sccsid = "@(#)addlink.c    8.1 (down!honey) 86/01/19";
  35. #endif lint
  36.  
  37. #include "def.h"
  38.  
  39. static link    *Trace[NTRACE];
  40. static int    Tracecount;
  41.  
  42. link    *
  43. addlink(from, to, cost, netchar, netdir)
  44. node    *from;
  45. register node    *to;
  46. Cost    cost;
  47. char    netchar;
  48. char    netdir;
  49. {
  50.     register link    *l, *prev = 0;
  51.  
  52.     if (Tflag)
  53.         ltrace(from, to, cost, netchar, netdir);
  54.     /* maintain uniqueness for dead links (only) */
  55.     for (l = from->n_link; l && l->l_flag & LDEAD; l = l->l_next) {
  56.         if (to == l->l_to) {
  57.             /* what the hell, use cheaper cost */
  58.             if (cost < l->l_cost) {
  59.                 l->l_cost = cost;
  60.                 netbits(l, netchar, netdir);
  61.             }
  62.             return(l);
  63.         }
  64.         prev = l;
  65.     }
  66.  
  67.     /* allocate and link in the new link struct */
  68.     l = newlink();
  69.     if (cost != INF)    /* ignore back links */
  70.         Lcount++;
  71.     if (prev) {
  72.         l->l_next = prev->l_next;
  73.         prev->l_next = l;
  74.     } else {
  75.         l->l_next = from->n_link;
  76.         from->n_link = l;
  77.     }
  78.  
  79.     l->l_to = to;
  80.     l->l_cost = cost;
  81.     if (netchar == 0) {
  82.         netchar = DEFNET;
  83.         netdir = DEFDIR;
  84.     }
  85.     netbits(l, netchar, netdir);
  86.  
  87.     return(l);
  88. }
  89.  
  90. link    *
  91. addgateway(from, to, cost, netchar, netdir)
  92. node    *from;
  93. node    *to;
  94. Cost    cost;
  95. char    netchar;
  96. char    netdir;
  97. {
  98.     register link    *l;
  99.  
  100.     l = addlink(from, to, cost, netchar, netdir);
  101.     l->l_flag |= LGATEWAY;
  102.     return(l);
  103. }
  104.  
  105. deadlink(s) 
  106. char    *s;
  107. {
  108.     char    *t, c;
  109.     link    *l;
  110.  
  111.     t = index(s, '!');
  112.     if (t) {
  113.         c = *t;
  114.         *t = 0;
  115.         l = addlink(addnode(s), addnode(t + 1), INF / 2, c, DEFDIR);
  116.         l->l_flag |= LDEAD;
  117.     } else 
  118.         addnode(s)->n_flag |= NDEAD;
  119. }
  120.  
  121. netbits(l, netchar, netdir)
  122. link    *l;
  123. char    netchar, netdir;
  124. {
  125.     char    *nptr;
  126.  
  127.     if ((nptr = index(Netchars, netchar)) == 0) {
  128.         fprintf(stderr, "%s: unknown network operator: %c\n",
  129.                                 ProgName, netchar);
  130.         badmagic(1);
  131.     }
  132.     l->l_flag &= ~(LNETCHARS|LDIR);
  133.     l->l_flag |= (nptr - Netchars) | dirbits(netdir);
  134. }
  135.  
  136. tracelink(arg) 
  137. char    *arg;
  138. {
  139.     char    *bang;
  140.     link    *l;
  141.  
  142.     if (Tracecount >= NTRACE)
  143.         return(-1);
  144.     l = newlink();
  145.     bang = index(arg, '!');
  146.     if (bang) {
  147.         *bang = 0;
  148.         l->l_to = addnode(bang+1);
  149.     } else 
  150.         l->l_to = 0;
  151.  
  152.     l->l_from = (link *) addnode(arg);
  153.     Trace[Tracecount++] = l;
  154.     return(0);
  155. }
  156.  
  157. STATIC
  158. ltrace(from, to, cost, netchar, netdir)
  159. node    *from, *to;
  160. Cost    cost;
  161. char    netchar;
  162. char    netdir;
  163. {
  164.     link    *l;
  165.     int    i;
  166.  
  167.     for (i = 0; i < Tracecount; i++) {
  168.         l = Trace[i];
  169.         /* overkill -- you asked for it! */
  170.         if ((l->l_to == 0
  171.           && (from == (node *) l->l_from || to == (node *) l->l_from))
  172.          || (from == (node *) l->l_from && to == l->l_to)
  173.          || (to == (node *) l->l_from && from == l->l_to)) {
  174.             ltrprint(from, to, cost, netchar, netdir);
  175.             return;
  176.         }
  177.     }
  178. }
  179.  
  180. /* print a trace item */
  181. STATIC
  182. ltrprint(from, to, cost, netchar, netdir)
  183. node    *from, *to;
  184. Cost    cost;
  185. char    netchar;
  186. char    netdir;
  187. {
  188.     char    buf[256], *bptr = buf;
  189.  
  190.     strcpy(bptr, from->n_name);
  191.     bptr += strlen(bptr);
  192.     *bptr++ = ' ';
  193.     if (netdir == LRIGHT)            /* @% */
  194.         *bptr++ = netchar;
  195.     strcpy(bptr, to->n_name);
  196.     bptr += strlen(bptr);
  197.     if (netdir == LLEFT)            /* !: */
  198.         *bptr++ = netchar;
  199.     sprintf(bptr, "(%ld)", cost);
  200.     yyerror(buf);
  201. }
  202.  
  203. atrace(n1, n2)
  204. node    *n1, *n2;
  205. {
  206.     link    *l;
  207.     int    i;
  208.     char    buf[256];
  209.  
  210.     for (i = 0; i < Tracecount; i++) {
  211.         l = Trace[i];
  212.         if (l->l_to == 0 && ((node *) l->l_from == n1 || (node *) l->l_from == n2)) {
  213.             sprintf(buf, "%s = %s", n1->n_name, n2->n_name);
  214.             yyerror(buf);
  215.             return;
  216.         }
  217.     }
  218. }
  219. SHAR_EOF
  220. if test 3358 -ne "`wc -c < 'addlink.c'`"
  221. then
  222.     echo shar: error transmitting "'addlink.c'" '(should have been 3358 characters)'
  223. fi
  224. fi
  225. echo shar: extracting "'addnode.c'" '(6585 characters)'
  226. if test -f 'addnode.c'
  227. then
  228.     echo shar: will not over-write existing file "'addnode.c'"
  229. else
  230. cat << \SHAR_EOF > 'addnode.c'
  231. /* pathalias -- by steve bellovin, as told to peter honeyman */
  232. #ifndef lint
  233. static char    *sccsid = "@(#)addnode.c    8.1 (down!honey) 86/01/19";
  234. #endif
  235.  
  236. #include "def.h"
  237.  
  238. extern void    lowercase(), rehash();
  239. extern node    *isprivate();
  240. extern long    hash();
  241.  
  242. /*
  243.  * these numbers are chosen because:
  244.  *    -> they are prime,
  245.  *    -> they are monotonic increasing,
  246.  *    -> each is a tad smaller than a multiple of 1024,
  247.  *    -> they form a fibonacci sequence (almost).
  248.  * the first point yields good hash functions, the second is used for the
  249.  * standard re-hashing implementation of open addressing, the third
  250.  * optimizes for quirks in some mallocs i have seen, and the fourth simply
  251.  * appeals to me.
  252.  */
  253. static int Primes[]    = {
  254. #ifndef SQUANDER
  255.     1021, 2039, 3067, 5113, 8179,
  256. #endif
  257.     13309, 21499, 0
  258. };
  259.  
  260. static int    Tabindex = -1;
  261. static int    Collision;    /* mark host name collisions in hash() */
  262.  
  263. node    *
  264. addnode(name)
  265. register char    *name;
  266. {
  267.     register long    i;
  268.     register node    *n;
  269.  
  270.     if (Iflag)
  271.         lowercase(name);
  272.  
  273.     /* is it a private host? */
  274.     n = isprivate(name);
  275.     if (n)
  276.         return(n);
  277.  
  278.     i = hash(name, 0);
  279.     if (Table[i]) 
  280.         return(Table[i]);
  281.  
  282.     n = newnode();
  283.     n->n_name = strsave(name);
  284.     Table[i] = n;
  285.     n->n_tloc = i;    /* essentially a back link to the table */
  286.     if (Collision)
  287.         n->n_flag |= COLLISION;    /* name collision with private host */
  288.  
  289.     return(n);
  290. }
  291.  
  292. alias(n1, n2)
  293. node    *n1, *n2;
  294. {
  295.     link    *l;
  296.     extern link *addlink();
  297.  
  298.     l = addlink(n1, n2, (Cost) 0, DEFNET, DEFDIR);
  299.     l->l_flag |= LALIAS;
  300.     l = addlink(n2, n1, (Cost) 0, DEFNET, DEFDIR);
  301.     l->l_flag |= LALIAS;
  302.     if (Tflag)
  303.         atrace(n1, n2);
  304. }
  305.  
  306. /*
  307.  * fold a string into a long int.  this algorithm ignores all but the last
  308.  * eight bytes, which affects < 15% of all host names, many of which have
  309.  * common prefixes anyway.
  310.  */
  311. STATIC long
  312. fold(str)
  313. register char    *str;
  314. {
  315.     register long    sum;
  316.  
  317.     sum = *str++;
  318.     while (*str) {
  319.         sum <<= 4;
  320.         sum += *str++;
  321.     }
  322.     if (sum < 0) 
  323.         sum = -sum;
  324.     return(sum);
  325. }
  326.  
  327. #define HASH1(n) ((n) % Tabsize);
  328. #define HASH2(n) (Tabsize - 2 - ((n) % (Tabsize-2)))    /* princeton!rs */
  329.  
  330. /*
  331.  * with a 0.75 high water mark, probes per access should be 1.84.
  332.  * use long constant to force promotion.
  333.  */
  334. #define HIGHWATER    75L
  335. #define isfull(n, size)    ((n) > ((size) * HIGHWATER) / 100)
  336.  
  337. STATIC long
  338. hash(name, unique)
  339. char    *name;
  340. {
  341.     register long    probe, hash2;
  342.     register node    *n;
  343.  
  344.     if (Tabindex < 0) {            /* first time */
  345.         Tabindex = 0;
  346.         Tabsize = Primes[0];
  347.         Table = newtable(Tabsize);
  348.     } else if (isfull(Ncount, Tabsize))
  349.         rehash();            /* more, more! */
  350.                 
  351.     probe = fold(name);
  352.     /* don't change the order of the next two lines */
  353.     hash2 = HASH2(probe);
  354.     probe = HASH1(probe);
  355.     /* thank you! */
  356.  
  357.     /*
  358.      * probe the hash table.
  359.      * if unique is set, we require a fresh slot.
  360.      * otherwise, use double hashing to find either
  361.      *  (1) an empty slot, or
  362.      *  (2) a non-private copy of this host name
  363.      *
  364.      * as a side effect, if we notice a collision with a private host
  365.      * we mark the other so that it is skipped at output time.
  366.      */
  367.     Collision = 0;
  368.     while ((n = Table[probe]) != 0) {
  369.         if (strcmp(n->n_name, name) == 0) {
  370.             if (unique)
  371.                 n->n_flag |= COLLISION;
  372.             else if (n->n_flag & ISPRIVATE)
  373.                 Collision++;
  374.             else
  375.                 break;    /* this is it! */
  376.         }
  377.         probe -= hash2;
  378.         if (probe < 0)
  379.             probe += Tabsize;
  380.     }
  381.     return(probe);
  382. }
  383.  
  384. STATIC void
  385. rehash()
  386. {
  387.     register node    **otable, **optr;
  388.     register long    probe;
  389.     long    osize;
  390.  
  391. #ifdef DEBUG
  392.     hashanalyze();
  393. #endif
  394.     optr = Table + Tabsize - 1;    /* ptr to last */
  395.     otable = Table;
  396.     osize = Tabsize;
  397.     Tabsize = Primes[++Tabindex];
  398.     if (Tabsize == 0) {    /* need more prime numbers */
  399.         fprintf(stderr, "%s: > %d hosts\n", ProgName, Primes[Tabindex-1]);
  400.         badmagic(1);
  401.     }
  402.     vprintf(stderr, "rehash into %d\n", Tabsize);
  403.     Table = newtable(Tabsize);
  404.  
  405.     do {
  406.         if (*optr == 0)
  407.             continue;    /* empty slot in old table */
  408.         probe = hash((*optr)->n_name, (*optr)->n_flag & ISPRIVATE);
  409.         if (Table[probe] != 0) {
  410.             fprintf(stderr, "%s: rehash error\n", ProgName);
  411.             badmagic(1);
  412.         }
  413.         Table[probe] = *optr;
  414.         (*optr)->n_tloc = probe;
  415.     } while (optr-- > otable);
  416.     freetable(otable, osize);
  417. }
  418.  
  419. hashanalyze()
  420. {
  421.     long    probe, hash2;
  422.     int    count, i, collision[8];
  423.     int    longest = 0, total = 0, slots = 0;
  424.     int    nslots = sizeof(collision)/sizeof(collision[0]);
  425.  
  426.     if (!Vflag)
  427.         return;
  428.  
  429.     strclear((char *) collision, sizeof(collision));
  430.     for (i = 0; i < Tabsize; i++) {
  431.         if (Table[i] == 0)
  432.             continue;
  433.         /* private hosts too hard to account for ... */
  434.         if (Table[i]->n_flag & ISPRIVATE)
  435.             continue;
  436.         count = 1;
  437.         probe = fold(Table[i]->n_name);
  438.         /* don't change the order of the next two lines */
  439.         hash2 = HASH2(probe);
  440.         probe = HASH1(probe);
  441.         /* thank you! */
  442.         while (Table[probe] != 0
  443.             && strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
  444.             count++;
  445.             probe -= hash2;
  446.             if (probe < 0)
  447.                 probe += Tabsize;
  448.         }
  449.         if (Table[probe] == 0) {
  450.             fprintf(stderr, "%s: impossible hash error for %s\n",
  451.                     ProgName, Table[i]->n_name);
  452.             badmagic(1);
  453.         }
  454.         
  455.         total += count;
  456.         slots++;
  457.         if (count > longest)
  458.             longest = count;
  459.         if (count >= nslots)
  460.             count = 0;
  461.         collision[count]++;
  462.     }
  463.     for (i = 1; i < nslots; i++)
  464.         if (collision[i])
  465.             fprintf(stderr, "%d chains: %d (%ld%%)\n",
  466.                 i, collision[i], (collision[i] * 100L)/ slots);
  467.         if (collision[0])
  468.             fprintf(stderr, "> %d chains: %d (%ld%%)\n",
  469.                 nslots - 1, collision[0],
  470.                 (collision[0] * 100L)/ slots);
  471.     fprintf(stderr, "%2.2f probes per access, longest chain: %d\n",
  472.         (double) total / slots, longest);
  473. }
  474.  
  475. STATIC void
  476. lowercase(s)
  477. register char    *s;
  478. {
  479.     do {
  480.         if (isupper(*s))
  481.             *s -= 'A' - 'a';    /* assumes ASCII */
  482.     } while (*s++);
  483. }
  484.  
  485. /*
  486.  * this might have to be recoded for performance if privates catch on
  487.  */
  488. STATIC node    *
  489. isprivate(name)
  490. register char    *name;
  491. {
  492.     register node    *n;
  493.  
  494.     for (n = Private; n != 0; n = n->n_private)
  495.         if (strcmp(name, n->n_name) == 0)
  496.             return(n);
  497.     return(0);
  498. }
  499.  
  500. fixprivate()
  501. {
  502.     register node    *n, *next;
  503.     register long    i;
  504.  
  505.     for (n = Private; n != 0; n = next) {
  506.         n->n_flag |= ISPRIVATE;        /* overkill, but safe */
  507.         i = hash(n->n_name, 1);
  508.         if (Table[i] != 0) {
  509.             fprintf(stderr, "%s: impossible private node error on %s\n",
  510.                 ProgName, n->n_name);
  511.             badmagic(1);
  512.         }
  513.     
  514.         Table[i] = n;
  515.         n->n_tloc = i;    /* essentially a back link to the table */
  516.         next = n->n_private;
  517.         n->n_private = 0;    /* clear for later use */
  518.     }
  519.     Private = 0;
  520. }
  521.  
  522. node    *
  523. addprivate(name)
  524. register char    *name;
  525. {
  526.     register node    *n;
  527.  
  528.     if (Iflag)
  529.         lowercase(name);
  530.     if ((n = isprivate(name)) != 0)
  531.         return(n);
  532.  
  533.     n = newnode();
  534.     n->n_name = strsave(name);
  535.     n->n_private = Private;
  536.     Private = n;
  537.     return(n);
  538. }
  539. SHAR_EOF
  540. if test 6585 -ne "`wc -c < 'addnode.c'`"
  541. then
  542.     echo shar: error transmitting "'addnode.c'" '(should have been 6585 characters)'
  543. fi
  544. fi
  545. echo shar: extracting "'extern.c'" '(650 characters)'
  546. if test -f 'extern.c'
  547. then
  548.     echo shar: will not over-write existing file "'extern.c'"
  549. else
  550. cat << \SHAR_EOF > 'extern.c'
  551. /* pathalias -- by steve bellovin, as told to peter honeyman */
  552. #ifndef lint
  553. static char    *sccsid = "@(#)extern.c    8.1 (down!honey) 86/01/19";
  554. #endif lint
  555.  
  556. #include "def.h"
  557.  
  558. node    *Home;
  559. char    *Cfile;
  560. char    **Ifiles;
  561. char    *ProgName;
  562. int    Vflag;
  563. int    Cflag;
  564. int    Iflag;
  565. int    Tflag;
  566. int    Lineno = 1;
  567. char    *Netchars = "!:@%";    /* sparse, but sufficient */
  568. int    Ncount;
  569. int    Lcount;
  570. char    *Graphout;
  571. char    *Linkout;
  572. node    **Table;        /* hash table + priority queue */
  573. long    Tabsize;        /* size of Table */    
  574. node    *Private;        /* list of private nodes in this file */
  575. long    Hashpart;        /* used while mapping -- above is heap */
  576. int    Scanstate = NEWLINE;    /* scanner (yylex) state */
  577. SHAR_EOF
  578. if test 650 -ne "`wc -c < 'extern.c'`"
  579. then
  580.     echo shar: error transmitting "'extern.c'" '(should have been 650 characters)'
  581. fi
  582. fi
  583. echo shar: extracting "'local.c'" '(1426 characters)'
  584. if test -f 'local.c'
  585. then
  586.     echo shar: will not over-write existing file "'local.c'"
  587. else
  588. cat << \SHAR_EOF > 'local.c'
  589. /* pathalias -- by steve bellovin, as told to peter honeyman */
  590. #ifndef lint
  591. static char    *sccsid = "@(#)local.c    8.1 (down!honey) 86/01/19";
  592. #endif lint
  593.  
  594. #include <stdio.h>
  595. #include "config.h"
  596.  
  597. #ifdef    UNAME
  598. #include <sys/utsname.h>
  599.  
  600. char    *
  601. local()
  602. {
  603.     static struct utsname utsname;
  604.  
  605.     uname(&utsname);
  606.     return(utsname.nodename);
  607. }
  608.  
  609. #else !UNAME
  610.  
  611. char    *
  612. local()
  613. {
  614.     static char lname[64];
  615.     void    gethostname();
  616.  
  617.     gethostname(lname, sizeof(lname));
  618.     return(lname);
  619. }
  620.  
  621. #ifndef GETHOSTNAME
  622.  
  623. static void
  624. gethostname(name, len)
  625. char    *name;
  626. {
  627.     FILE    *whoami, *fopen(), *popen();
  628.     char    *ptr, *index();
  629.  
  630.     *name = '\0';
  631.  
  632.     /* try /etc/whoami */
  633.     if ((whoami = fopen("/etc/whoami", "r")) != 0) {
  634.         (void) fgets(name, len, whoami);
  635.         (void) fclose(whoami);
  636.         if ((ptr = index(name, '\n')) != 0)
  637.             *ptr = '\0';
  638.     }
  639.     if (*name)
  640.         return;
  641.  
  642.     /* try /usr/include/whoami.h */
  643.     if ((whoami = fopen("/usr/include/whoami.h", "r")) != 0) {
  644.         while (!feof(whoami)) {
  645.             char    buf[100];
  646.  
  647.             if (fgets(buf, 100, whoami) == 0)
  648.                 break;
  649.             if (sscanf(buf, "#define sysname \"%[^\"]\"", name))
  650.                 break;
  651.         }
  652.         (void) fclose(whoami);
  653.         if (*name)
  654.             return;
  655.     }
  656.  
  657.     /* ask uucp */
  658.     if ((whoami = popen("uuname -l", "r")) != 0) {
  659.         (void) fgets(name, len, whoami);
  660.         (void) pclose(whoami);
  661.         if ((ptr = index(name, '\n')) != 0)
  662.             *ptr = '\0';
  663.     }
  664.     if (*name)
  665.         return;
  666.     
  667.     /* aw hell, i give up!  is this a real unix? */
  668.     return;
  669. }
  670. #endif GETHOSTNAME
  671. #endif UNAME
  672. SHAR_EOF
  673. if test 1426 -ne "`wc -c < 'local.c'`"
  674. then
  675.     echo shar: error transmitting "'local.c'" '(should have been 1426 characters)'
  676. fi
  677. fi
  678. echo shar: extracting "'main.c'" '(2362 characters)'
  679. if test -f 'main.c'
  680. then
  681.     echo shar: will not over-write existing file "'main.c'"
  682. else
  683. cat << \SHAR_EOF > 'main.c'
  684. /* pathalias -- by steve bellovin, as told to peter honeyman */
  685. #ifndef lint
  686. static char    *sccsid = "@(#)main.c    8.1 (down!honey) 86/01/19";
  687. #endif
  688.  
  689. #define MAIN    /* for sccsid in header files */
  690.  
  691. #include "def.h"
  692.  
  693. #define USAGE "usage: %s [-vci] [-l localname] [-d deadlink] [-t tracelink] [-g file] [-s file]\n"
  694.  
  695. main(argc, argv) 
  696. int    argc; 
  697. char    *argv[];
  698. {
  699.     char    *locname = 0;
  700.     int    c, errflg = 0;
  701.  
  702.     ProgName = argv[0];
  703.     (void) allocation();    /* initialize data space monitoring */
  704.     Cfile = "[deadlinks]";    /* for tracing dead links */
  705.     while ((c = getopt(argc, argv, "cd:g:il:s:t:v")) != EOF)
  706.         switch(c) {
  707.         case 'c':    /* print cost info */
  708.             Cflag++;
  709.             break;
  710.         case 'd':    /* dead host or link */
  711.             deadlink(optarg);
  712.             break;
  713.         case 'g':    /* graph output file */
  714.             Graphout = optarg;
  715.             break;
  716.         case 'i':    /* ignore case */
  717.             Iflag++;
  718.             break;
  719.         case 'l':    /* local name */
  720.             locname = optarg;
  721.             break;
  722.         case 's':    /* show shortest path tree */
  723.             Linkout = optarg;
  724.             break;
  725.         case 't':    /* trace this link */
  726.             if (tracelink(optarg) < 0) {
  727.                 fprintf(stderr, "%s: can trace only %d links\n", ProgName, NTRACE);
  728.                 exit(1);
  729.             }
  730.             Tflag = 1;
  731.             break;
  732.         case 'v':    /* verbose stderr, mixed blessing */
  733.             Vflag++;
  734.             break;
  735.         default:
  736.             errflg++;
  737.         }
  738.  
  739.     if (errflg) {
  740.         fprintf(stderr, USAGE, ProgName);
  741.         exit(1);
  742.     }
  743.     argv += optind;        /* kludge for yywrap() */
  744.  
  745.     if (*argv) {
  746.         Ifiles = argv;
  747.         freopen("/dev/null", "r", stdin);
  748.     }
  749.  
  750.     if (!locname) 
  751.         locname = local();
  752.     if (*locname == 0) {
  753.         locname = "lostinspace";
  754.         fprintf(stderr, "%s: using \"%s\" for local name\n",
  755.                 ProgName, locname);
  756.     }
  757.  
  758.     Home = addnode(locname);    /* add home node */
  759.     Home->n_cost = 0;        /* doesn't cost to get here */
  760.  
  761.     yyparse();            /* read in link info */
  762.  
  763.     if (Vflag > 1)
  764.         hashanalyze();
  765.     vprintf(stderr, "%d vertices, %d edges\n", Ncount, Lcount);
  766.     vprintf(stderr, "allocation is %ldk after parsing\n", allocation());
  767.  
  768.     Cfile = "[backlinks]";    /* for tracing back links */
  769.     Lineno = 0;
  770.  
  771.     mapit();            /* compute shortest path tree */
  772.     vprintf(stderr, "allocation is %ldk after mapping\n", allocation());
  773.  
  774.     printit();            /* traverse tree and print paths */
  775.     vprintf(stderr, "allocation is %ldk after printing\n", allocation());
  776.  
  777.     exit(0);
  778. }
  779.  
  780. badmagic(n)
  781. {
  782.     if (n) {
  783.         fprintf(stderr, "%s: cannot recover!\n", ProgName);
  784. #ifdef DEBUG
  785.         abort();
  786. #else
  787.         exit(n);
  788. #endif
  789.     }
  790. }
  791. SHAR_EOF
  792. if test 2362 -ne "`wc -c < 'main.c'`"
  793. then
  794.     echo shar: error transmitting "'main.c'" '(should have been 2362 characters)'
  795. fi
  796. fi
  797. echo shar: extracting "'makedb.c'" '(2348 characters)'
  798. if test -f 'makedb.c'
  799. then
  800.     echo shar: will not over-write existing file "'makedb.c'"
  801. else
  802. cat << \SHAR_EOF > 'makedb.c'
  803. /* pathalias -- by steve bellovin, as told to peter honeyman */
  804. #ifndef lint
  805. static char    *sccsid = "@(#)makedb.c    8.1 (down!honey) 86/01/19";
  806. #endif lint
  807.  
  808. #include <stdio.h>
  809. #include "config.h"
  810.  
  811. typedef struct {
  812.     char *dptr;
  813.     int dsize;
  814. } datum;
  815.  
  816. char *Ofile = ALIASDB, *ProgName;
  817.  
  818. #define USAGE "%s [-o dbmname] [-a] [file ...]"
  819.  
  820. main(argc, argv)
  821.     char *argv[];
  822. {    char *ofptr;
  823.     int c, append = 0;
  824.     extern int optind;
  825.     extern char *optarg;
  826.  
  827.     ProgName = argv[0];
  828.     while ((c = getopt(argc, argv, "o:av")) != EOF)
  829.         switch(c) {
  830.         case 'o':    /* dbm output file */
  831.             Ofile = optarg;
  832.             break;
  833.  
  834.         case 'a':    /* append mode */
  835.             append++;
  836.             break;
  837.  
  838.         default:
  839.             fprintf(stderr, USAGE, ProgName);
  840.             exit(1);
  841.             break;
  842.         }
  843.  
  844.  
  845.     if ((ofptr = rindex(Ofile, '/')) != 0)
  846.         ofptr++;
  847.     else
  848.         ofptr = Ofile;
  849.     if (strlen(ofptr) > 10) {
  850.         ofptr[10] = 0;
  851.         fprintf(stderr, "%s: using %s for dbm output\n", ProgName, Ofile);
  852.     }
  853.  
  854.     if (append == 0 && dbfile(Ofile) != 0) {
  855.         perror_(Ofile);
  856.         exit(1);
  857.     }
  858.  
  859.     if (dbminit(Ofile) < 0) {
  860.         perror_(Ofile);
  861.         exit(1);
  862.     }
  863.  
  864.     if (optind == argc)
  865.         makedb((char *) 0);
  866.     else for ( ; optind < argc; optind++)
  867.         makedb(argv[optind]);
  868.     exit(0);
  869. }
  870.  
  871. dbfile(dbf)
  872.     char *dbf;
  873. {
  874.     return (dbcreat(dbf, "dir") != 0 || dbcreat(dbf, "pag") != 0);
  875. }
  876.  
  877. dbcreat(dbf, suffix)
  878.     char *dbf, *suffix;
  879. {    char buf[BUFSIZ];
  880.     int fd;
  881.  
  882.     (void) sprintf(buf, "%s.%s", dbf, suffix);
  883.     if ((fd = creat(buf, 0666)) < 0)
  884.         return(-1);
  885.     (void) close(fd);
  886.     return(0);
  887. }
  888.  
  889.  
  890. makedb(ifile)
  891.     char *ifile;
  892. {    char line[BUFSIZ];
  893.     datum key, val;
  894.  
  895.     if (ifile && (freopen(ifile, "r", stdin) == NULL)) {
  896.         perror_(ifile);
  897.         return;
  898.     }
  899.  
  900.     /*
  901.      * keys and values are 0 terminated.  this wastes time and (disk) space,
  902.      * but does lend simplicity and backwards compatibility.
  903.      */
  904.     key.dptr = line;
  905.     while (fgets(line, sizeof(line), stdin) != NULL) {
  906.         char *op, *end;
  907.  
  908.         end = line + strlen(line);
  909.         end[-1] = 0;    /* kill newline, stuff null terminator */
  910.         op = index(line, '\t');
  911.         if (op != 0) {
  912.             *op++ = 0;
  913.             key.dsize = op - line;        /* 0 terminated */
  914.             val.dptr = op;
  915.             val.dsize = end - op;        /* 0 terminated */
  916.         } else {
  917.             key.dsize = end - line;        /* 0 terminated */
  918.             val.dptr = "\0";        /* why must i do this? */
  919.             val.dsize = 1;
  920.         }
  921.         if (store(key, val) < 0)
  922.             perror_(Ofile);
  923.     }
  924. }
  925.  
  926. perror_(str)
  927.     char    *str;
  928. {
  929.     fprintf(stderr, "%s: ", ProgName);
  930.     perror(str);
  931. }
  932. SHAR_EOF
  933. if test 2348 -ne "`wc -c < 'makedb.c'`"
  934. then
  935.     echo shar: error transmitting "'makedb.c'" '(should have been 2348 characters)'
  936. fi
  937. fi
  938. echo shar: extracting "'mapaux.c'" '(5168 characters)'
  939. if test -f 'mapaux.c'
  940. then
  941.     echo shar: will not over-write existing file "'mapaux.c'"
  942. else
  943. cat << \SHAR_EOF > 'mapaux.c'
  944. /* pathalias -- by steve bellovin, as told to peter honeyman */
  945. #ifndef lint
  946. static char    *sccsid = "@(#)mapaux.c    8.1 (down!honey) 86/01/19";
  947. #endif lint
  948.  
  949. #include "def.h"
  950.  
  951. void    pack();
  952.  
  953. void
  954. pack()
  955. {
  956.     long    hole, next;
  957.  
  958.     /* find first "hole " */
  959.     for (hole = Tabsize - 1; hole >= 0 && Table[hole] != 0; --hole)
  960.         ;
  961.  
  962.     /* repeatedly move next filled entry into last hole */
  963.     for (next = hole - 1; next >= 0; --next) {
  964.         if (Table[next] != 0) {
  965.             Table[hole] = Table[next];
  966.             Table[hole]->n_tloc = hole;
  967.             Table[next] = 0;
  968.             while (Table[--hole] != 0)    /* find next hole */
  969.                 ;
  970.         }
  971.     }
  972.     Hashpart = hole + 1;
  973. }
  974.  
  975. FILE    *Gstream;
  976.  
  977. dumpgraph()
  978. {
  979.     long    i;
  980.     node    *n;
  981.  
  982.     if ((Gstream = fopen(Graphout, "w")) == NULL) {
  983.         fprintf(stderr, "%s: ", ProgName);
  984.         perror(Graphout);
  985.     }
  986.  
  987.     untangle();    /* untangle net cycles for proper output */
  988.  
  989.     for (i = Hashpart; i < Tabsize; i++) {
  990.         n = Table[i];
  991.         if (n == 0)
  992.             continue;    /* impossible, but ... */
  993.         /* a minor optimization ... */
  994.         if (n->n_link == 0)
  995.             continue;
  996.         /* pathparse doesn't need these */
  997.         if (n->n_flag & NNET)
  998.             continue;
  999.         dumpnode(n);
  1000.     }
  1001. }
  1002.  
  1003. dumpnode(from)
  1004. node    *from;
  1005. {
  1006.     node    *to;
  1007.     link    *l;
  1008.     char    netbuf[BUFSIZ], *nptr = netbuf;
  1009.  
  1010.     for (l = from->n_link ; l; l = l->l_next) {
  1011.         to = l->l_to;
  1012.         if (from == to)
  1013.             continue;    /* oops -- it's me! */
  1014.  
  1015.         if ((to->n_flag & NNET) == 0) {
  1016.             /* host -> host -- print host>host */
  1017.             if (l->l_cost == INF)
  1018.                 continue;    /* phoney link */
  1019.             fputs(from->n_name, Gstream);
  1020.             putc('>', Gstream);
  1021.             fputs(to->n_name, Gstream);
  1022.             putc('\n', Gstream);
  1023.         } else {
  1024.             /* host -> net -- just cache it for now */
  1025.             while (to->n_root && to != to->n_root)
  1026.                 to = to->n_root;
  1027.             *nptr++ = ',';
  1028.             strcpy(nptr, to->n_name);
  1029.             nptr += strlen(nptr);
  1030.         }
  1031.     }
  1032.  
  1033.     /* dump nets */
  1034.     if (nptr != netbuf) {
  1035.         /* nets -- print host@\tnet,net, ... */
  1036.         *nptr = 0;
  1037.         fputs(from->n_name, Gstream);
  1038.         putc('@', Gstream);
  1039.         *netbuf = '\t';    /* insert tab by killing initial ',' */
  1040.         fputs(netbuf, Gstream);    /* skip initial ',' */
  1041.         putc('\n', Gstream);
  1042.     }
  1043. }
  1044.  
  1045. /*
  1046.  * remove cycles in net definitions. 
  1047.  *
  1048.  * depth-first search
  1049.  *
  1050.  * for each net, run dfs on its neighbors (nets only).  if we return to
  1051.  * a visited node, that's a net cycle.  mark the cycle with a pointer
  1052.  * in the n_root field (which gets us closer to the root of this
  1053.  * portion of the dfs tree).
  1054.  */
  1055. untangle()
  1056. {
  1057.     long    i;
  1058.     node    *n;
  1059.  
  1060.     for (i = Hashpart; i < Tabsize; i++) {
  1061.         n = Table[i];
  1062.         if (n == 0 || (n->n_flag & NNET) == 0 || n->n_root)
  1063.             continue;
  1064.         dfs(n);
  1065.     }
  1066. }
  1067.  
  1068. dfs(n)
  1069. node    *n;
  1070. {
  1071.     link    *l;
  1072.     node    *next;
  1073.  
  1074.     n->n_flag |= INDFS;
  1075.     n->n_root = n;
  1076.     for (l = n->n_link; l; l = l->l_next) {
  1077.         next = l->l_to;
  1078.         if ((next->n_flag & NNET) == 0)
  1079.             continue;
  1080.         if ((next->n_flag & INDFS) == 0) {
  1081.             dfs(next);
  1082.             if (next->n_root != next)
  1083.                 n->n_root = next->n_root;
  1084.         } else
  1085.             n->n_root = next->n_root;
  1086.     }
  1087.     n->n_flag &= ~INDFS;
  1088. }
  1089.  
  1090. showlinks() 
  1091. {
  1092.     link    *l;
  1093.     node    *n;
  1094.     long    i;
  1095.     FILE    *estream;
  1096.  
  1097.     if ((estream = fopen(Linkout, "w")) == 0)
  1098.         return;
  1099.  
  1100.     for (i = Hashpart; i < Tabsize; i++) {
  1101.         n = Table[i];
  1102.         if (n == 0)    /* impossible, but ... */
  1103.             continue;
  1104.         if (l = n->n_link) {
  1105.             fprintf(estream, "%s\t%s(%d)", n->n_name,
  1106.                 l->l_to->n_name,
  1107.                 l->l_cost ? l->l_cost : DEFCOST);
  1108.             for (l = l->l_next; l; l = l->l_next)
  1109.                 fprintf(estream, ",\n\t%s(%d)", l->l_to->n_name,
  1110.                     l->l_cost ? l->l_cost : DEFCOST);
  1111.             fputc('\n', estream);
  1112.         }
  1113.     }
  1114.     (void) fclose(estream);
  1115. }
  1116.  
  1117. /*
  1118.  * n is node in heap, newp is candidate for new parent.
  1119.  * choose between newp and n->n_parent for parent.
  1120.  * return 0 to use newp, non-zero o.w.
  1121.  */
  1122. #define NEWP 0
  1123. #define OLDP 1
  1124. tiebreaker(n, newp)
  1125. node    *n, *newp;
  1126. {
  1127.     register char    *opname, *npname, *name;
  1128.     node    *oldp;
  1129.     int    metric;
  1130.  
  1131.     oldp = n->n_parent;
  1132.  
  1133.     /*
  1134.      * given the choice of going through a gatewayed not or not,
  1135.      * choose the latter, placating the FCC or whatever.
  1136.      */
  1137.     if (GATEWAYED(newp) && !GATEWAYED(oldp))
  1138.         return(oldp);
  1139.     if (!GATEWAYED(newp) && GATEWAYED(oldp))
  1140.         return(newp);
  1141.  
  1142.     /* look at real parents, not nets */
  1143.     while (oldp->n_flag & NNET)
  1144.         oldp = oldp->n_parent;
  1145.     while (newp->n_flag & NNET)
  1146.         newp = newp->n_parent;
  1147.  
  1148.     /* use fewer hops, if possible */
  1149.     metric = height(oldp) - height(newp);
  1150.     if (metric < 0)
  1151.         return(OLDP);
  1152.     if (metric > 0)
  1153.         return(NEWP);
  1154.  
  1155.     /* compare names */
  1156.     opname = oldp->n_name;
  1157.     npname = newp->n_name;
  1158.     name = n->n_name;
  1159.  
  1160.     /* find point of departure */
  1161.     while (*opname == *npname && *npname == *name) {
  1162.         if (*name == 0) {
  1163.             fprintf(stderr, "%s: error in tie breaker\n", ProgName);
  1164.             badmagic(1);
  1165.         }
  1166.         opname++;
  1167.         npname++;
  1168.         name++;
  1169.     }
  1170.  
  1171.     /* use longest match, if appl. */
  1172.     if (*opname == *name || *opname == 0)
  1173.         return(OLDP);
  1174.     if (*npname == *name || *npname == 0)
  1175.         return(NEWP);
  1176.  
  1177.     /* use shorter host name, if appl. */
  1178.     metric = strlen(opname) - strlen(npname);
  1179.     if (metric < 0)
  1180.         return(OLDP);
  1181.     if (metric > 0)
  1182.         return(NEWP);
  1183.  
  1184.     /* use larger lexicographically (no reason) */
  1185.     metric = strcmp(opname, npname);
  1186.     if (metric < 0)
  1187.         return(NEWP);
  1188.     return(OLDP);
  1189. }
  1190.  
  1191. height(n)
  1192. register node    *n;
  1193. {
  1194.     register int i = 0;
  1195.  
  1196.     while ((n = n->n_parent) != 0)
  1197.         if ((n->n_flag & NNET) == 0)
  1198.             i++;    /* should count domains too ... */
  1199.     return(i);
  1200. }
  1201. SHAR_EOF
  1202. if test 5168 -ne "`wc -c < 'mapaux.c'`"
  1203. then
  1204.     echo shar: error transmitting "'mapaux.c'" '(should have been 5168 characters)'
  1205. fi
  1206. fi
  1207. echo shar: extracting "'mapit.c'" '(10469 characters)'
  1208. if test -f 'mapit.c'
  1209. then
  1210.     echo shar: will not over-write existing file "'mapit.c'"
  1211. else
  1212. cat << \SHAR_EOF > 'mapit.c'
  1213. /* pathalias -- by steve bellovin, as told to peter honeyman */
  1214. #ifndef lint
  1215. static char    *sccsid = "@(#)mapit.c    8.1 (down!honey) 86/01/19";
  1216. #endif
  1217.  
  1218. #include "def.h"
  1219.  
  1220. /* privates */
  1221. extern void    reheap(), insert(), heapswap();
  1222. extern link    *min_node(), *rmlink();
  1223. extern Cost    costof();
  1224.  
  1225. static long    Nheap;
  1226. static long    Heaphighwater;
  1227. static link    **Heap;
  1228.  
  1229.  
  1230. /* transform the graph to a shortest-path tree by marking tree edges */
  1231.  
  1232. mapit()
  1233. {
  1234.     register node *n, *next;
  1235.     register link *l;
  1236.     link    *lprev, *lnext;
  1237.     Cost cost;
  1238.  
  1239.     /*
  1240.      * re-use the hash table space for the heap.
  1241.      */
  1242.     Heap = (link **) Table;
  1243.  
  1244.     pack();        /* remove holes in the Table */
  1245.     if (Linkout && *Linkout)    /* dump cheapest links */
  1246.         showlinks();
  1247.     if (Graphout && *Graphout)    /* dump the edge list */
  1248.         dumpgraph();
  1249.  
  1250.     /* invent and insert a link for Home to get things started */
  1251.     l = newlink();
  1252.     l->l_to = Home;
  1253.     (void) dehash(Home);
  1254.     insert(l);
  1255.  
  1256.     /* main mapping loop */
  1257. remap:
  1258.     Heaphighwater = Nheap;
  1259.     while ((l = min_node()) != 0) {
  1260.         l->l_flag |= LTREE;
  1261.         n = l->l_to;
  1262.         n->n_flag |= MAPPED;
  1263.  
  1264.         /* add children to heap */
  1265.         lprev = 0;
  1266.         for (l = n->n_link; l != 0; l = lnext) {
  1267.  
  1268.             next = l->l_to;        /* neighboring node */
  1269.             if (next->n_flag & MAPPED) {
  1270.                 lnext = rmlink(l, lprev, n);
  1271.                 continue;
  1272.             }
  1273.             cost = costof(n, l);
  1274.  
  1275.             if (skiplink(l, n, cost)) {
  1276.                 lnext = rmlink(l, lprev, n);
  1277.                 continue;
  1278.             }
  1279.  
  1280.             /*
  1281.              * put this link in the heap, in a place where it may
  1282.              * percolate up, but not down.  if new, or if cost is
  1283.              * being increased, move to end.  otherwise, cost is
  1284.              * same or less, so leave it where it is.  unfortunately,
  1285.              * freeing a link already in the heap is too costly at
  1286.              * this point.
  1287.              *
  1288.              * TODO: avoid heaping aliases and network members.
  1289.              */
  1290.             if (dehash(next) == 0)    /* first time in heap */
  1291.                 insert(l);    /* insert at end */
  1292.             else {
  1293.                 /* replace heaped link by this one */
  1294.                 if (cost > next->n_cost) {    /* gateway */
  1295.                     /* move old link to end of heap */
  1296.                     heapswap((long) (next->n_tloc), Nheap);
  1297.                     next->n_tloc = Nheap;
  1298.                 }
  1299.                 Heap[next->n_tloc] = l;
  1300.             }
  1301.                 
  1302.             next->n_cost = cost;
  1303.             next->n_parent = n;
  1304.             reheap(l);        /* restore heap property */
  1305.  
  1306.             /*
  1307.              * note whether we got here via a gatewayed net.
  1308.              * domains are presumed to require gateways.
  1309.              * aliases inherit parent's gateway status.
  1310.              */
  1311.             next->n_flag &= ~GATEWAYIN;
  1312.             if (l->l_flag & LALIAS)
  1313.                 next->n_flag |= (n->n_flag & GATEWAYIN);
  1314.             else if (GATEWAYED(n))
  1315.                 next->n_flag |= GATEWAYIN;
  1316.             lprev = l;    /* this link's a keeper */
  1317.             lnext = l->l_next;
  1318.         }
  1319.  
  1320.     }
  1321.     vprintf(stderr, "heap high water mark was %d\n", Heaphighwater);
  1322.  
  1323.     /* sanity check on implementation */
  1324.     if (Nheap != 0) {
  1325.         fprintf(stderr, "%s: null entry found in heap\n", ProgName);
  1326.         badmagic(1);
  1327.     }
  1328.  
  1329.     if (Hashpart < Tabsize) {
  1330.         /*
  1331.          * add back links from unreachable hosts to reachable
  1332.          * neighbors, then remap.  asymptotically, this is
  1333.          * quadratic.  in practice, this is done exactly once.
  1334.          */
  1335.         backlinks();
  1336.         if (Nheap)
  1337.             goto remap;
  1338.     }
  1339.     if (Hashpart < Tabsize) {
  1340.         fputs("You can't get there from here:\n", stderr);
  1341.         for ( ; Hashpart < Tabsize; Hashpart++) {
  1342.             fprintf(stderr, "\t%s", Table[Hashpart]->n_name);
  1343.             if (Table[Hashpart]->n_flag & (ISPRIVATE|COLLISION))
  1344.                 fputs(" (private)", stderr);
  1345.             putc('\n', stderr);
  1346.         }
  1347.     }
  1348. }
  1349.  
  1350. /*
  1351.  * can this link be ignored?  if yes, return 1, o.w. 0.
  1352.  * a link can be skipped if it is not in the shortest path tree.
  1353.  */
  1354. STATIC int
  1355. skiplink(l, parent, cost)
  1356. link    *l;            /* new link to this node */
  1357. node    *parent;        /* new parent of this node */
  1358. Cost    cost;            /* new cost to this node */
  1359. {
  1360.     node    *n;        /* this node */
  1361.     link    *lheap;        /* existing link to this node */
  1362.  
  1363.     n = l->l_to;
  1364.  
  1365.     /* first time we've reached this node? */
  1366.     if (n->n_tloc >= Hashpart)
  1367.         return(0);
  1368.  
  1369.     lheap = Heap[n->n_tloc];
  1370.  
  1371.     /* examine links to nets that require gateways */
  1372.     if (GATEWAYED(n)) {
  1373.         /* if exactly one is a gateway, use it */
  1374.         if ((lheap->l_flag & LGATEWAY) && !(l->l_flag & LGATEWAY))
  1375.             return(1);    /* old is gateway */
  1376.         if (!(lheap->l_flag & LGATEWAY) && (l->l_flag & LGATEWAY))
  1377.             return(0);    /* new is gateway */
  1378.  
  1379.         /* no gateway or both gateways;  resolve in standard way ... */
  1380.     }
  1381.  
  1382.     /* examine dup link (sanity check) */
  1383.     if (n->n_parent == parent && ((lheap->l_flag & LDEAD) || (l->l_flag & LDEAD))) {
  1384.         fprintf(stderr, "%s: dup dead link not eliminated: %s -> %s\n",
  1385.             ProgName, parent->n_name, n->n_name);
  1386.         badmagic(1);
  1387.     }
  1388.  
  1389.  
  1390.     /*  examine cost */
  1391.     if (cost < n->n_cost)
  1392.         return(0);
  1393.     if (cost > n->n_cost)
  1394.         return(1);
  1395.  
  1396.     /* all other things being equal, consult the oracle */
  1397.     return(tiebreaker(n, parent));
  1398. }
  1399.  
  1400. STATIC Cost
  1401. costof(prev, l)
  1402. register node    *prev;
  1403. register link    *l;
  1404. {
  1405.     register node    *next;
  1406.     register Cost    cost;
  1407.  
  1408.     next = l->l_to;
  1409.  
  1410.     if (l->l_flag & LALIAS) {
  1411.         /* copy left/right bits */
  1412.         next->n_flag &= ~(HASLEFT|HASRIGHT);
  1413.         next->n_flag |= (prev->n_flag & (HASLEFT|HASRIGHT));
  1414.         return(prev->n_cost);    /* by definition */
  1415.     }
  1416.  
  1417.         
  1418.     cost = prev->n_cost + l->l_cost;    /* basic cost */
  1419.  
  1420.     /*
  1421.      * heuristics:
  1422.      *    charge for a dead link.
  1423.      *    charge for getting out of a dead host.
  1424.      *    charge for getting into a gatewayed net (except at a gateway).
  1425.      *    discourage mixing of left and right syntax when next is a host.
  1426.      *    charge for leaving a gatewayed net.
  1427.      *
  1428.      * life was simpler when pathalias computed true shortest paths.
  1429.      */
  1430.     if (l->l_flag & LDEAD)        /* dead link */
  1431.         cost += INF/2;
  1432.     if (DEADHOST(prev))        /* dead host */
  1433.         cost += INF/2;
  1434.     if (GATEWAYED(next) && !(l->l_flag & LGATEWAY))    /* not gateway */
  1435.         cost += INF/2;
  1436.     if (!ISANET(next)) {
  1437.         /* charge for mixed syntax here */
  1438.         if ((NETDIR(l) == LLEFT && (prev->n_flag & HASRIGHT))
  1439.          || (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
  1440.             cost += DEFCOST;
  1441.     }
  1442.     /*
  1443.      * if reached by a gatewayed net, discourage further links.
  1444.      * this has some relevance to common carriers and the FCC ...
  1445.      * the penalty inheres to hosts, not aliases, nets, or domains.
  1446.      */
  1447.     if ((prev->n_flag & GATEWAYIN) && !ISADOMAIN(prev) && !(prev->n_flag & NNET))
  1448.         cost += INF/2;    /* heavyweight, but appropriate */
  1449.  
  1450.     /* set left/right bits */
  1451.     next->n_flag &= ~(HASLEFT|HASRIGHT);
  1452.     if (NETDIR(l) == LLEFT || (prev->n_flag & HASLEFT))
  1453.         next->n_flag |= HASLEFT;
  1454.     if (NETDIR(l) == LRIGHT || (prev->n_flag & HASRIGHT))
  1455.         next->n_flag |= HASRIGHT;
  1456.  
  1457.     return(cost);
  1458. }
  1459.  
  1460. STATIC link *
  1461. rmlink(l, lprev, n)
  1462. link    *l, *lprev;
  1463. node    *n;
  1464. {
  1465.     link    *lnext;
  1466.  
  1467.     lnext = l->l_next;
  1468.     if (lprev)
  1469.         lprev->l_next = l->l_next;
  1470.     else
  1471.         n->n_link = l->l_next;
  1472.     free((char *) l);
  1473.     return(lnext);
  1474. }
  1475.  
  1476. /*
  1477.  * binary heap implementation of priority queue.
  1478.  * TODO: make the heap smaller by giving inserting a placeholder
  1479.  * for net members when the net is extracted.  this requires storing the
  1480.  * cost of a net in the net node itself -- yuck.  is it worth it?
  1481.  */
  1482.  
  1483. STATIC void
  1484. insert(l)
  1485. link    *l;
  1486. {
  1487.     register node    *n;
  1488.  
  1489.     n = l->l_to;
  1490.     Heap[n->n_tloc] = 0;
  1491.     if (Heap[Nheap+1] != 0) {
  1492.         fprintf(stderr, "%s: heap error in insert\n", ProgName);
  1493.         badmagic(1);
  1494.     }
  1495.     if (Nheap++ == 0) {
  1496.         Heap[1] = l;
  1497.         n->n_tloc = 1;
  1498.         return;
  1499.     }
  1500.     if (Vflag && Nheap > Heaphighwater)
  1501.         Heaphighwater = Nheap;    /* diagnostics */
  1502.  
  1503.     /* insert at the end.  caller must reheap(). */
  1504.     Heap[Nheap] = l;
  1505.     n->n_tloc = Nheap;
  1506. }
  1507.  
  1508. /*
  1509.  * replace existing link in heap by this one, then
  1510.  * "percolate" up the heap by exchanging with the parent
  1511.  */
  1512. STATIC void
  1513. reheap(l)
  1514. link    *l;
  1515. {
  1516.     register long    loc, parent;
  1517.     register Cost    cost;
  1518.     register node    *n, *np;
  1519.  
  1520.     n = l->l_to;
  1521.  
  1522.     cost = n->n_cost;
  1523.     for (loc = n->n_tloc; loc > 1; loc = parent) {
  1524.         parent = loc / 2;
  1525.         /* sanity check on implementation */
  1526.         if (Heap[parent] == 0) {
  1527.             fprintf(stderr, "%s: heap error in insert\n", ProgName);
  1528.             badmagic(1);
  1529.         }
  1530.         np = Heap[parent]->l_to;
  1531.         if (cost > np->n_cost)
  1532.             return;
  1533.         /* move nets below hosts for output stability */
  1534.         if (cost == np->n_cost && ((n->n_flag & NNET) || !(np->n_flag & NNET)))
  1535.             return;
  1536.         heapswap(loc, parent);
  1537.     }
  1538. }
  1539.  
  1540. /* extract min (== Heap[1]) from heap */
  1541. STATIC link    *
  1542. min_node()
  1543. {
  1544.     link *rval;
  1545.     register link **regheap;
  1546.     register long    i, child;
  1547.     
  1548.     if (Nheap == 0)
  1549.         return(0);
  1550.  
  1551.     regheap = Heap;        /* in register -- heavily used */
  1552.     rval = regheap[1];    /* return this one */
  1553.             
  1554.     /* move last entry into root, percolate down */
  1555.     regheap[1] = regheap[Nheap];
  1556.     regheap[1]->l_to->n_tloc = 1;
  1557.     regheap[Nheap] = 0;
  1558.     if (--Nheap == 0)
  1559.         return(rval);
  1560.  
  1561.     i = 1;
  1562.     for (;;) {
  1563.         /* swap with smaller child down the tree */
  1564.         child = i * 2;    /* lhs child is 2i, rhs is 2i+1. */
  1565.         if (child >= Nheap)
  1566.             return(rval);
  1567.         /* use rhs child if smaller than lhs child */
  1568.         if (regheap[child]->l_to->n_cost > regheap[child+1]->l_to->n_cost
  1569.          || (regheap[child]->l_to->n_cost == regheap[child+1]->l_to->n_cost
  1570.           && !ISANET(regheap[child+1]->l_to)))
  1571.             child++;
  1572.             
  1573.         if (regheap[i]->l_to->n_cost < regheap[child]->l_to->n_cost)
  1574.             return(rval);
  1575.         /* move nets below hosts for output stability */
  1576.         if (regheap[i]->l_to->n_cost == regheap[child]->l_to->n_cost
  1577.          && (!ISANET(regheap[i]->l_to) || ISANET(regheap[child]->l_to)))
  1578.             return(rval);
  1579.         heapswap(i, child);
  1580.         i = child;
  1581.     }
  1582.     /*NOTREACHED*/
  1583. }
  1584.  
  1585. /* exchange Heap[i] and Heap[j] pointers */
  1586. STATIC void
  1587. heapswap(i, j)
  1588. long    i, j;
  1589. {
  1590.     register link    *temp, **regheap;
  1591.  
  1592.     regheap = Heap;    /* heavily used -- put in register */
  1593.     temp = regheap[i];
  1594.     regheap[i] = regheap[j];
  1595.     regheap[j] = temp;
  1596.     regheap[j]->l_to->n_tloc = j;
  1597.     regheap[i]->l_to->n_tloc = i;
  1598. }
  1599.  
  1600. /* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
  1601. dehash(n)
  1602. register node    *n;
  1603. {
  1604.     if (n->n_tloc < Hashpart)
  1605.         return(1);
  1606.  
  1607.     /* swap with entry in Table[Hashpart] */
  1608.     Table[Hashpart]->n_tloc = n->n_tloc;
  1609.     Table[n->n_tloc] = Table[Hashpart];
  1610.     Table[Hashpart] = n;
  1611.  
  1612.     n->n_tloc = Hashpart++;
  1613.     return(0);
  1614. }
  1615.  
  1616. backlinks()
  1617. {
  1618.     link *l;
  1619.     node *n, *parent, *nomap;
  1620.     long i;
  1621.  
  1622.     for (i = Hashpart; i < Tabsize; i++) {
  1623.         nomap = Table[i];
  1624.         parent = 0;
  1625.         for (l = nomap->n_link; l; l = l->l_next) {
  1626.             n = l->l_to;
  1627.             if (!(n->n_flag & MAPPED))
  1628.                 continue;
  1629.             if (parent == 0) {
  1630.                 parent = n;
  1631.                 continue;
  1632.             }
  1633.             if (n->n_cost > parent->n_cost)
  1634.                 continue;
  1635.             if (n->n_cost == parent->n_cost) {
  1636.                 nomap->n_parent = parent;
  1637.                 if (tiebreaker(nomap, n))
  1638.                     continue;
  1639.             }
  1640.             parent = n;
  1641.         }
  1642.         if (parent == 0)
  1643.             continue;
  1644.         (void) dehash(nomap);
  1645.         l = addlink(parent, nomap, INF, DEFNET, DEFDIR);
  1646.         nomap->n_parent = parent;
  1647.         nomap->n_cost = costof(parent, l);
  1648.         insert(l);
  1649.         reheap(l);
  1650.     }
  1651.     vprintf(stderr, "%d backlinks\n", Nheap);
  1652. }
  1653. SHAR_EOF
  1654. if test 10469 -ne "`wc -c < 'mapit.c'`"
  1655. then
  1656.     echo shar: error transmitting "'mapit.c'" '(should have been 10469 characters)'
  1657. fi
  1658. fi
  1659. echo shar: extracting "'mem.c'" '(3448 characters)'
  1660. if test -f 'mem.c'
  1661. then
  1662.     echo shar: will not over-write existing file "'mem.c'"
  1663. else
  1664. cat << \SHAR_EOF > 'mem.c'
  1665. /* pathalias -- by steve bellovin, as told to peter honeyman */
  1666. #ifndef lint
  1667. static char    *sccsid = "@(#)mem.c    8.1 (down!honey) 86/01/19";
  1668. #endif
  1669.  
  1670. #include "def.h"
  1671.  
  1672. /* imported */
  1673. extern char *sbrk();
  1674.  
  1675. link    *
  1676. newlink()
  1677. {
  1678.     link    *rval;
  1679.  
  1680.     if ((rval = (link * ) calloc(1, sizeof(link))) == 0)
  1681.         nomem();
  1682.     return(rval);
  1683. }
  1684.  
  1685. node    *
  1686. newnode()
  1687. {
  1688.     node    *rval;
  1689.  
  1690.     if ((rval = (node * ) calloc(1, sizeof(node))) == 0)
  1691.         nomem();
  1692.     Ncount++;
  1693.     return(rval);
  1694. }
  1695.  
  1696. char    *
  1697. strsave(s)
  1698. char    *s;
  1699. {
  1700.     char *r;
  1701.  
  1702.     if ((r = malloc((unsigned int) strlen(s) + 1)) == 0)
  1703.         nomem();
  1704.     (void) strcpy(r, s);
  1705.     return(r);
  1706. }
  1707.  
  1708. #ifndef strclear
  1709. void
  1710. strclear(dst, len)
  1711. register char *dst;
  1712. register int len;
  1713. {
  1714.     while (--len >= 0)
  1715.         *dst++ = 0;
  1716. }
  1717. #endif /*strclear*/
  1718.  
  1719. node    **
  1720. newtable(size)
  1721. long    size;
  1722. {
  1723.     node    **rval;
  1724.  
  1725.     if ((rval = (node **) calloc(1, (unsigned int) (size * sizeof(*rval)))) == 0) 
  1726.         nomem();
  1727.     return(rval);
  1728. }
  1729.  
  1730. freetable(t, size)
  1731. node    **t;
  1732. long    size;
  1733. {
  1734. #ifdef MYMALLOC
  1735.     addtoheap((char *) t, (long) (size * sizeof(*t)));
  1736. #else
  1737.     free((char *) t);
  1738. #endif
  1739. }
  1740.  
  1741. nomem()
  1742. {
  1743.     fprintf(stderr, "%s: Out of memory (%ldk allocated)\n",
  1744.             ProgName, allocation());
  1745.     badmagic(1);
  1746. }
  1747.  
  1748. /* data space allocation -- main sets End very early */
  1749. allocation()
  1750. {
  1751.     static char    *dataspace;
  1752.  
  1753.     if (dataspace == 0) {    /* first time */
  1754.         dataspace = sbrk(0);        /* &end? */
  1755.         return(0);
  1756.     }
  1757.     return((sbrk(0) - dataspace)/1024);
  1758. }
  1759.  
  1760. #ifdef MYMALLOC
  1761.  
  1762. /* use c library malloc/calloc here, and here only */
  1763. #undef malloc
  1764. #undef calloc
  1765. extern char *malloc(), *calloc();
  1766.  
  1767. /* allocate in MBUFSIZ chunks.  4k works ok (less 16 for malloc quirks). */
  1768. #define MBUFSIZ (4 * 1024 - 16)
  1769.  
  1770. /* 
  1771.  * mess with ALIGN at your peril.  longword (== 0 mod 4)
  1772.  * alignment seems to work everywhere.
  1773.  */
  1774.  
  1775. #define ALIGN 2
  1776.  
  1777. typedef struct heap heap;
  1778. struct heap {
  1779.     heap *h_next;
  1780.     long h_size;
  1781. };
  1782.  
  1783. static heap *Mheap;    /* not to be confused with a priority queue */
  1784.  
  1785. addtoheap(p, size)
  1786. char *p;
  1787. long size;
  1788. {
  1789.     int adjustment;
  1790.     heap *pheap;
  1791.  
  1792.     /* p is aligned, but it doesn't hurt to check */
  1793.     adjustment = align(p);
  1794.     p += adjustment;
  1795.     size -= adjustment;
  1796.  
  1797.     if (size < 1024)
  1798.         return;        /* can't happen */
  1799.     pheap = (heap *) p;    /* pheap is shorthand */
  1800.     pheap->h_next = Mheap;
  1801.     pheap->h_size = size;
  1802.     Mheap = pheap;
  1803. }
  1804.  
  1805. /*
  1806.  * buffered malloc()
  1807.  *    returns space initialized to 0.  calloc isn't used, since
  1808.  *    strclear can be faster.
  1809.  *
  1810.  * free is ignored, except for very large objects,
  1811.  * which are returned to the heap with addtoheap(). 
  1812.  */
  1813.  
  1814. char    *
  1815. mymalloc(n)
  1816. register unsigned int    n;
  1817. {
  1818.     static long    size;        /* how much do we have on hand? */
  1819.     static char    *mstash;    /* where is it?  (kept aligned) */
  1820.     register char    *rval;
  1821.  
  1822.     n += align((char *) n);    /* keep everything aligned */
  1823.     if (n >= 1024) {        /* from hash table */
  1824.         rval = malloc(n);    /* aligned */
  1825.         strclear(rval, n);
  1826.         return(rval);
  1827.     }
  1828.     
  1829.  
  1830.     if (n > size) {
  1831.         /* look in the heap (already aligned) */
  1832.         if (Mheap) {
  1833.             mstash = (char *) Mheap;
  1834.             size = Mheap->h_size;
  1835.             Mheap = Mheap->h_next;
  1836.         } else {
  1837.             mstash = malloc(MBUFSIZ);    /* aligned */
  1838.             if (mstash == 0) {
  1839.                 size = 0;
  1840.                 return(0);
  1841.             }
  1842.             size = MBUFSIZ;
  1843.         }
  1844.         strclear(mstash, size);
  1845.     }
  1846.     rval = mstash;
  1847.     mstash += n;
  1848.     size -= n;
  1849.     return(rval);
  1850. }
  1851.  
  1852. /* what's the (mis-)alignment of n?  return the complement of (n mod 2^ALIGN) */
  1853. align(n)
  1854. char    *n;
  1855. {
  1856.     int    abits;    /* misalignment bits in n */
  1857.  
  1858.     abits = (int) n & ~(0xff << ALIGN) & 0xff;
  1859.     if (abits == 0)
  1860.         return(0);
  1861.     return((1 << ALIGN) - abits);
  1862. }
  1863.  
  1864. #endif /*MYMALLOC*/
  1865. SHAR_EOF
  1866. if test 3448 -ne "`wc -c < 'mem.c'`"
  1867. then
  1868.     echo shar: error transmitting "'mem.c'" '(should have been 3448 characters)'
  1869. fi
  1870. fi
  1871. echo shar: extracting "'printit.c'" '(3713 characters)'
  1872. if test -f 'printit.c'
  1873. then
  1874.     echo shar: will not over-write existing file "'printit.c'"
  1875. else
  1876. cat << \SHAR_EOF > 'printit.c'
  1877. /* pathalias -- by steve bellovin, as told to peter honeyman */
  1878. #ifndef lint
  1879. static char    *sccsid = "@(#)printit.c    8.1 (down!honey) 86/01/19";
  1880. #endif
  1881.  
  1882. #include "def.h"
  1883.  
  1884. /* use lots of char bufs -- profiling indicates this costs about 5 kbytes */
  1885.  
  1886. /* in practice, even the longest paths are < 100 bytes */
  1887. #define PSIZE 512
  1888.  
  1889. printit()
  1890. {    link *l;
  1891.     char pbuf[PSIZE];
  1892.  
  1893.     /* print home */
  1894.     if (Cflag)
  1895.         printf("%ld\t", (long) Home->n_cost);
  1896.     printf("%s\t%%s\n", Home->n_name);
  1897.     
  1898.     strcpy(pbuf, "%s");
  1899.     for (l = Home->n_link; l; l = l->l_next) {
  1900.         if (l->l_flag & LTREE) {
  1901.             preorder(l, pbuf);
  1902.             strcpy(pbuf, "%s");
  1903.         }
  1904.     }
  1905. }
  1906.  
  1907. /* preorder traversal of shortest path tree */
  1908. preorder(l, ppath)
  1909. register link *l;
  1910. char *ppath;
  1911. {
  1912.     register node *n;
  1913.     char npath[PSIZE];
  1914.  
  1915.     setpath(l, ppath, npath);
  1916.     n = l->l_to;
  1917.     if ((n->n_flag & NNET) || ISADOMAIN(n))
  1918.         printnet(n, npath, n->n_cost);
  1919.     else
  1920.         printhost(n, npath, n->n_cost);
  1921.     for (l = n->n_link; l; l = l->l_next)
  1922.         if (l->l_flag & LTREE)
  1923.             preorder(l, npath);
  1924. }
  1925.  
  1926. setpath(l, ppath, npath) 
  1927. link *l;
  1928. register char *ppath, *npath;
  1929. {
  1930.     register node *next;
  1931.     char netchar;
  1932.     extern char *hostpath();
  1933.  
  1934.     next = l->l_to;
  1935.     /*
  1936.      * for magic @-% conversion.
  1937.      * assume that gateways to domains want no @'s
  1938.      */
  1939.     if (next->n_parent->n_flag & ATSIGN || ISADOMAIN(next))
  1940.         next->n_flag |= ATSIGN;
  1941.  
  1942.     /* special handling for aliases , domains, and nets */
  1943.     if ((l->l_flag & LALIAS) || (next->n_flag & NNET) || ISADOMAIN(next)) {
  1944.         strcpy(npath, ppath);
  1945.         return;
  1946.     }
  1947.         
  1948.     netchar = NETCHAR(l);
  1949.     if (netchar == '@')
  1950.         if (next->n_flag & ATSIGN)
  1951.             netchar = '%';    /* shazam?  shaman? */
  1952.         else
  1953.             next->n_flag |= ATSIGN;
  1954.  
  1955.     /* remainder should be a sprintf -- foo on '%' as an operator */
  1956.     for ( ; *npath = *ppath; ppath++) {
  1957.         if (*ppath == '%') {
  1958.             switch(ppath[1]) {
  1959.             case 's':
  1960.                 ppath++;
  1961.                 npath = hostpath(npath, l, netchar);
  1962.                 break;
  1963.  
  1964.             case '%':
  1965.                 *++npath = *++ppath;
  1966.                 npath++;
  1967.                 break;
  1968.  
  1969.             default:
  1970.                 fprintf(stderr, "%s: %%%c found in setpath\n",
  1971.                         ProgName, ppath[1]);
  1972.                 badmagic(1);
  1973.                 break;
  1974.             }
  1975.         } else
  1976.             npath++;
  1977.     }
  1978. }
  1979.  
  1980. char *
  1981. hostpath(path, l, netchar)
  1982. register char *path;
  1983. register link *l;
  1984. char netchar;
  1985. {
  1986.     register node *prev;
  1987.  
  1988.     prev = l->l_to->n_parent;
  1989.     if (NETDIR(l) == LLEFT) {
  1990.         /* host!user */
  1991.         strcpy(path, l->l_to->n_name);
  1992.         path += strlen(path);
  1993.         while (ISADOMAIN(prev)) {
  1994.             strcpy(path, prev->n_name);
  1995.             path += strlen(path);
  1996.             prev = prev->n_parent;
  1997.         }
  1998.         *path++ = netchar;
  1999.         if (netchar == '%')
  2000.             *path++ = '%';
  2001.         *path++ = '%';
  2002.         *path++ = 's';
  2003.     } else {
  2004.         /* %s@host */
  2005.         *path++ = '%';
  2006.         *path++ = 's';
  2007.         *path++ = netchar;
  2008.         if (netchar == '%')
  2009.             *path++ = '%';
  2010.         strcpy(path, l->l_to->n_name);
  2011.         path += strlen(path);
  2012.         while (ISADOMAIN(prev)) {
  2013.             strcpy(path, prev->n_name);
  2014.             path += strlen(path);
  2015.             prev = prev->n_parent;
  2016.         }
  2017.     }
  2018.     return(path);
  2019. }
  2020.  
  2021. STATIC
  2022. printhost(n, path, cost)
  2023. node *n;
  2024. char *path;
  2025. Cost cost;
  2026. {
  2027.     /* for collisions, print the domained name only */
  2028.     if ((n->n_flag & (ISPRIVATE|COLLISION)) == 0) {
  2029.         if (Cflag)
  2030.             printf("%ld\t", (long) cost);
  2031.         fputs(n->n_name, stdout);
  2032.         putchar('\t');
  2033.         puts(path);
  2034.     } else if (ISADOMAIN(n->n_parent))
  2035.         printdomain(n, path, cost);    /* print fully qualified name */
  2036. }
  2037.  
  2038. STATIC
  2039. printnet(n, path, cost)
  2040. node *n;
  2041. char *path;
  2042. Cost cost;
  2043. {
  2044.     /* print gateways */
  2045.     if (!ISADOMAIN(n))
  2046.         return;
  2047.     /* if it's private, print only if qualifed */
  2048.     if ((n->n_flag & (ISPRIVATE|COLLISION)) && !ISADOMAIN(n->n_parent))
  2049.         return;
  2050.     printdomain(n, path, cost);
  2051. }
  2052.  
  2053. STATIC
  2054. printdomain(n, path, cost)
  2055. node *n;
  2056. char *path;
  2057. Cost cost;
  2058. {
  2059.     if (Cflag)
  2060.         printf("%ld\t", (long) cost);
  2061.     do {
  2062.         fputs(n->n_name, stdout);
  2063.         n = n->n_parent;
  2064.     } while (ISADOMAIN(n));
  2065.     putchar('\t');
  2066.     puts(path);
  2067. }
  2068. SHAR_EOF
  2069. if test 3713 -ne "`wc -c < 'printit.c'`"
  2070. then
  2071.     echo shar: error transmitting "'printit.c'" '(should have been 3713 characters)'
  2072. fi
  2073. fi
  2074. echo shar: extracting "'parse.y'" '(7502 characters)'
  2075. if test -f 'parse.y'
  2076. then
  2077.     echo shar: will not over-write existing file "'parse.y'"
  2078. else
  2079. cat << \SHAR_EOF > 'parse.y'
  2080. %{
  2081. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2082. #ifndef lint
  2083. static char    *sccsid = "@(#)parse.y    8.1 (down!honey) 86/01/19";
  2084. #endif lint
  2085.  
  2086. #include "def.h"
  2087.  
  2088. /* I thank Paul Haahr and Greg Noel for helping to clean this up. */
  2089. %}
  2090.  
  2091. %union {
  2092.     node    *y_node;
  2093.     Cost    y_cost;
  2094.     char    y_net;
  2095.     char    *y_name;
  2096.     struct {
  2097.         node *ys_node;
  2098.         Cost ys_cost;
  2099.         char ys_net;
  2100.         char ys_dir;
  2101.     } y_s;
  2102. }
  2103.  
  2104. %type <y_s>    site
  2105. %type <y_node>    links aliases plist network nlist host Psite Site
  2106. %type <y_cost>    cost cexpr
  2107.  
  2108. %token <y_name>    SITE HOST
  2109. %token <y_cost>    COST
  2110. %token <y_net>    NET
  2111. %token NL PRIVATE
  2112.  
  2113. %left    '+' '-'
  2114. %left    '*' '/'
  2115.  
  2116. %%
  2117. map    :    /* empty */
  2118.     |    map        NL
  2119.     |    map links    NL
  2120.     |    map aliases    NL
  2121.     |    map network    NL
  2122.     |    map private    NL
  2123.     |    error        NL
  2124.     ;
  2125.  
  2126. links    : host site cost {
  2127.         if (GATEWAYED($2.ys_node))
  2128.             addgateway($1, $2.ys_node, $3, $2.ys_net, $2.ys_dir);
  2129.         else
  2130.             addlink($1, $2.ys_node, $3, $2.ys_net, $2.ys_dir);
  2131.       }
  2132.                 
  2133.     | links ',' site cost {
  2134.         if (GATEWAYED($3.ys_node))
  2135.             addgateway($1, $3.ys_node, $4, $3.ys_net, $3.ys_dir);
  2136.         else
  2137.             addlink($1, $3.ys_node, $4, $3.ys_net, $3.ys_dir);
  2138.       }
  2139.     | links ','    /* permit this benign error */
  2140.     ;
  2141.  
  2142. aliases    : host '=' Site        {alias($1, $3);}
  2143.     | aliases ',' Site    {alias($1, $3);}
  2144.     | aliases ','    /* permit this benign error */
  2145.     ;
  2146.  
  2147. network    : host '=' '{' nlist '}' cost    {fixnet($1, $4, $6, DEFNET, DEFDIR);}
  2148.     | host '=' NET '{' nlist '}' cost    {fixnet($1, $5, $7, $3, LRIGHT);}
  2149.     | host '=' '{' nlist '}' NET cost    {fixnet($1, $4, $7, $6, LLEFT);}
  2150.     ;
  2151.  
  2152. private    : PRIVATE '{' plist '}' ;
  2153.  
  2154. host    : HOST        {$$ = addnode($1);}
  2155.     | PRIVATE    {$$ = addnode("private");}
  2156.     ;
  2157.  
  2158. Site    : SITE    {$$ = addnode($1);} ;
  2159.  
  2160. site    : Site {
  2161.         $$.ys_node = $1;
  2162.         $$.ys_net = DEFNET;
  2163.         $$.ys_dir = DEFDIR;
  2164.       }
  2165.     | NET Site {
  2166.         $$.ys_node = $2;
  2167.         $$.ys_net = $1;
  2168.         $$.ys_dir = LRIGHT;
  2169.       }
  2170.     | Site NET {
  2171.         $$.ys_node = $1;
  2172.         $$.ys_net = $2;
  2173.         $$.ys_dir = LLEFT;
  2174.       }
  2175.     ;
  2176.  
  2177. Psite    : SITE    {$$ = addprivate($1);} ;
  2178.  
  2179. plist    : Psite        {$1->n_flag |= ISPRIVATE;}
  2180.     | plist ',' Psite    {$3->n_flag |= ISPRIVATE;}
  2181.     | plist ','    /* permit this benign error  */
  2182.     ;
  2183.  
  2184. nlist    : Site
  2185.     | nlist ',' Site {
  2186.         if ($3->n_net == 0) {
  2187.             $3->n_net = $1;
  2188.             $$ = $3;
  2189.         }
  2190.       }
  2191.     | nlist ','    /* permit this benign error */
  2192.     ;
  2193.         
  2194. cost    : {$$ = DEFCOST;    /* empty -- cost is always optional */}
  2195.     | '(' {Scanstate = COSTING;} cexpr {Scanstate = OTHER;} ')'
  2196.         {$$ = $3;}
  2197.     ;
  2198.  
  2199. cexpr    : COST
  2200.     | '(' cexpr ')'   {$$ = $2;}
  2201.     | cexpr '+' cexpr {$$ = $1 + $3;}
  2202.     | cexpr '-' cexpr {$$ = $1 - $3;}
  2203.     | cexpr '*' cexpr {$$ = $1 * $3;}
  2204.     | cexpr '/' cexpr {
  2205.         if ($3 == 0)
  2206.             yyerror("zero divisor\n");
  2207.         else
  2208.             $$ = $1 / $3;
  2209.       }
  2210.     ;
  2211. %%
  2212.  
  2213. yyerror(s)
  2214. char *s;
  2215. {
  2216.     /* a concession to bsd error(1) */
  2217.     if (Cfile)
  2218.         fprintf(stderr, "\"%s\", ", Cfile);
  2219.     else
  2220.         fprintf(stderr, "%s: ", ProgName);
  2221.     fprintf(stderr, "line %d: %s\n", Lineno, s);
  2222. }
  2223.  
  2224. /*
  2225.  * patch in the costs of getting on/off the network.
  2226.  *
  2227.  * for each network member on netlist, add links:
  2228.  *    network -> member    cost = 0;
  2229.  *    member -> network    cost = parameter.
  2230.  *
  2231.  * if network and member both require gateways, assume network
  2232.  * is a gateway to member (but not v.v., to avoid such travesties
  2233.  * as topaz!seismo.css.gov.edu.rutgers).
  2234.  *
  2235.  * note that members can have varying costs to a network, by suitable
  2236.  * multiple declarations.  this is a feechur, albeit a useless one.
  2237.  */
  2238. fixnet(network, nlist, cost, netchar, netdir)
  2239. register node    *network;
  2240. node    *nlist;
  2241. Cost    cost;
  2242. char    netchar, netdir;
  2243. {
  2244.     register node    *member, *nextnet;
  2245.     link    *l;
  2246.  
  2247.     network->n_flag |= NNET;
  2248.  
  2249.     /* now insert the links */
  2250.     for (member = nlist ; member; member = nextnet) {
  2251.         /* network -> member, cost is 0 */
  2252.         if (GATEWAYED(network) && GATEWAYED(member))
  2253.             (void) addgateway(network, member, (Cost) 0, netchar, netdir);
  2254.         else
  2255.             (void) addlink(network, member, (Cost) 0, netchar, netdir);
  2256.  
  2257.         /* member -> network, cost is parameter */
  2258.         (void) addlink(member, network, cost, netchar, netdir);
  2259.         nextnet = member->n_net;
  2260.         member->n_net = 0;    /* clear for later use */
  2261.     }
  2262. }
  2263.  
  2264. /* scanner */
  2265.  
  2266. #define LBRACE '{'
  2267. #define RBRACE '}'
  2268. #define LPAREN '('
  2269. #define RPAREN ')'
  2270. #define QUOTE '"'
  2271.  
  2272. Cost isacost();
  2273.  
  2274. yylex()
  2275. {
  2276.     register int    c;
  2277.     Cost    cost;
  2278.     char    buf[BUFSIZ], errbuf[128];
  2279.  
  2280. tailrecursion:
  2281.     if (feof(stdin) && yywrap())
  2282.         return(EOF);
  2283.  
  2284.     if ((c = getchar()) == EOF)
  2285.         goto tailrecursion;
  2286.  
  2287.     while (c == ' ' || c == '\t')
  2288.         c = getchar();
  2289.  
  2290.     if (c == '\n') {
  2291.         Lineno++;
  2292.         c = getchar();
  2293.         if (c == ' ' || c == '\t')
  2294.             goto tailrecursion;
  2295.         ungetc(c, stdin);
  2296.         Scanstate = NEWLINE;
  2297.         return(NL);
  2298.     }
  2299.  
  2300.     if (c == '#') {
  2301.         while ((c = getchar()) != '\n')
  2302.             if (c == EOF)
  2303.                 goto tailrecursion;
  2304.         ungetc(c, stdin);
  2305.         goto tailrecursion;
  2306.     }
  2307.  
  2308.     ungetc(c, stdin);
  2309.  
  2310.     switch(Scanstate) {
  2311.     case COSTING:
  2312.         if (isdigit(c)) {
  2313.             cost = 0;
  2314.             for (c = getchar(); isdigit(c); c = getchar())
  2315.                 cost = (cost * 10) + c - '0';
  2316.  
  2317.             ungetc(c, stdin);
  2318.             yylval.y_cost = cost;
  2319.             return(COST);
  2320.         }
  2321.  
  2322.         
  2323.         if (getword(buf) == 0) {
  2324.             if ((yylval.y_cost = isacost(buf)) == 0) {
  2325.                 sprintf(errbuf, "unknown cost (%s), using default", buf);
  2326.                 yyerror(errbuf);
  2327.                 yylval.y_cost = DEFCOST;
  2328.             }
  2329.             return(COST);
  2330.         }
  2331.  
  2332.         return(getchar());    /* can't be EOF */
  2333.  
  2334.     case NEWLINE:
  2335.         Scanstate = OTHER;
  2336.         if (getword(buf) != 0)
  2337.             return(getchar());    /* can't be EOF */
  2338.         /* `private' (but not `"private"')? */
  2339.         if (c == 'p' && strcmp(buf, "private") == 0)
  2340.             return(PRIVATE);
  2341.  
  2342.         yylval.y_name = buf;
  2343.         return(HOST);
  2344.     }
  2345.  
  2346.     if (getword(buf) == 0) {
  2347.         yylval.y_name = buf;
  2348.         return(SITE);
  2349.     }
  2350.  
  2351.     c = getchar();    /* can't be EOF */
  2352.  
  2353.     if (index(Netchars, c)) {
  2354.         yylval.y_net = c;
  2355.         return(NET);
  2356.     }
  2357.  
  2358.     return(c);
  2359. }
  2360.  
  2361. /*
  2362.  * fill str with the next word in [0-9A-Za-z][-._0-9A-Za-z]+ or a quoted
  2363.  * string that contains no newline.  return -1 on failure or EOF, 0 o.w.
  2364.  */ 
  2365. getword(str)
  2366. register char    *str;
  2367. {
  2368.     register int    c;
  2369.  
  2370.     c = getchar();
  2371.     if (c == QUOTE) {
  2372.         for ( ; (*str = getchar()) != '"'; str++) {
  2373.             if (*str == '\n') {
  2374.                 yyerror("newline in quoted string\n");
  2375.                 ungetc('\n', stdin);
  2376.                 return(-1);
  2377.             }
  2378.         }
  2379.         *str = 0;
  2380.         return(0);
  2381.     }
  2382.  
  2383.     /* host name must start with alphanumeric or `.' */
  2384.     if (!isalnum(c) && c != '.') {
  2385.         ungetc(c, stdin);
  2386.         return(-1);
  2387.     }
  2388.  
  2389. yymore:
  2390.     do {
  2391.         *str++ = c;
  2392.         c = getchar();
  2393.     } while (isalnum(c) || c == '.' || c == '_');
  2394.  
  2395.     if (c == '-' && Scanstate != COSTING)
  2396.         goto yymore;
  2397.  
  2398.     ungetc(c, stdin);
  2399.     *str = 0;
  2400.     return(0);
  2401. }
  2402.  
  2403. static struct ctable {
  2404.     char *cname;
  2405.     Cost cval;
  2406. } ctable[] = {
  2407.     /*
  2408.      * this list is searched sequentially (with strcmps!).
  2409.      * it is too long.  (they are ordered by frequency of
  2410.      * appearance in a "typical" dataset.)
  2411.      *
  2412.      * adding a 0 cost token breaks isacost().  don't do it.
  2413.      */
  2414.     {"DEMAND", 300},
  2415.     {"DAILY", 5000},
  2416.     {"DIRECT", 200},
  2417.     {"EVENING", 1800},
  2418.     {"LOCAL", 25},
  2419.     {"LOW", 5},    /* baud rate penalty */
  2420.     {"HOURLY", 500},
  2421.     {"POLLED", 5000},
  2422.     {"DEDICATED", 95},
  2423.     {"WEEKLY", 30000},
  2424.     {"DEAD", INF/2},
  2425.     {"HIGH", -5},    /* baud rate bonus */
  2426.     /* the remainder are reviled */
  2427.     {"ARPA", 100},
  2428.     {"DIALED", 300},
  2429.     {"A", 300},
  2430.     {"B", 500},
  2431.     {"C", 1800},
  2432.     {"D", 5000},
  2433.     {"E", 30000},
  2434.     {"F", INF/2},
  2435.     0
  2436. };
  2437.  
  2438. STATIC Cost
  2439. isacost(buf)
  2440. register char    *buf;
  2441. {
  2442.     register struct ctable    *ct;
  2443.  
  2444.     for (ct = ctable; ct->cname; ct++)
  2445.         if (strcmp(buf, ct->cname) == 0)
  2446.             return(ct->cval);
  2447.  
  2448.     return((Cost) 0);
  2449. }
  2450.  
  2451. yywrap()
  2452. {
  2453.     char    errbuf[100];
  2454.  
  2455.     fixprivate();    /* munge private host definitions */
  2456.  
  2457.     if (Ifiles == 0) 
  2458.         return(1);
  2459.  
  2460.     fclose(stdin);
  2461.     while (*Ifiles) {
  2462.         Lineno = 1;
  2463.         if (fopen((Cfile = *Ifiles++), "r"))
  2464.             return(0);
  2465.         sprintf(errbuf, "%s: %s", ProgName, Cfile);
  2466.         perror(errbuf);
  2467.     }
  2468.     return(1);
  2469. }
  2470. SHAR_EOF
  2471. if test 7502 -ne "`wc -c < 'parse.y'`"
  2472. then
  2473.     echo shar: error transmitting "'parse.y'" '(should have been 7502 characters)'
  2474. fi
  2475. fi
  2476. exit 0
  2477. #    End of shell archive
  2478.